package org.example.l0;

import org.junit.jupiter.api.Test;

public class isMatchPattern {

    @Test
    void isMatch() {
        boolean aa = isMatch("aa", "a*");
        System.out.println(aa);
    }

    public boolean isMatch(String s,
                           String p) {
        int len1 = s.length(), len2 = p.length();
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 0; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                char c = p.charAt(j - 1);
                if (c == '*') {
                    dp[i][j] = dp[i][j - 2] || (matchs(s, p, i, j - 1) && dp[i - 1][j]);
                } else {
                    dp[i][j] = matchs(s, p, i, j) ? dp[i - 1][j - 1] : false;
                }
            }
        }

        return dp[len1][len2];
    }

    boolean matchs(String s,
                   String p,
                   int i,
                   int j) {
        if (i == 0) {
            return false;
        }

        char bChar = p.charAt(j - 1);
        if (bChar == '.') {
            return true;
        }

        return s.charAt(i - 1) == p.charAt(j - 1);
    }

}
